package U_A.PEU.P.image;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.util.List;
import java.util.Vector;

/*
 * 个人著作权人, 作者 罗瑶光, 浏阳
 * yaoguangluo@outlook.com, 313699483@qq.com, 2080315360@qq.com,
 * (lyg.tin@gmail.com2018年回国后因国内G网屏蔽不再使用）
 * 15116110525-浏阳德塔软件开发有限公司-创始人-法人-总经理-永久非盈利-
 * 430181198505250014, G24402609, EB0581342
 * 204925063, 389418686, F2406501, 0626136
 * 湖南省 浏阳市 集里街道 神仙坳社区 大塘冲一段路 208号 阳光家园别墅小区 第十栋别墅 第三层
 * */
//奇怪，之前我refer Google 搜索的边界文字那段，今天优化新陈代谢，发现不见了，那就再注释下。
/*
 * 作者 罗瑶光, 浏阳
 * yaoguangluo@outlook.com, 313699483@qq.com, 2080315360@qq.com, -
 ** 15116110525-浏阳德塔软件开发有限公司-创始人-法人-总经理-永久非盈利-
 * 430181198505250014, G24402609, EB0581342
 * 204925063, 389418686, F2406501, 0626136
 * 湖南省 浏阳市 集里街道 神仙坳社区 大塘冲路一段
*  208号 阳光家园别墅小区 第十栋别墅 第三层
 * */
public class ConvexHull {
    double seconds;
    public List<Vertex> convexHull(List<Vertex> vertices) {
        List<Vertex> polygon = new Vector<Vertex>();
        int sx, lx;
        Vertex vcurr = null;
        Vertex vnext = null;
        int i, x;
        lx = vertices.get(0).x;
        sx = vertices.get(0).x;
        for (i = 1; i < vertices.size(); i++) {
            x = vertices.get(i).x;
            if (x > lx) lx = x;
            if (x < sx) sx = x;
        }
        for (Vertex v : vertices) {
            if (v.x == sx && (vcurr == null || v.y > vcurr.y)) {
                vcurr = v;
            }
        }
        int dxs, dys;
        int dxc, dyc;
        int dxt, dyt;
        int lqc, lqt;
        int scmp;
        polygon.add(vcurr);
        dys = 1;
        dxs = 0;
        while (vcurr.x <= lx) {
            dyc = -1;
            dxc = 0;
            lqc = 0;
            for (Vertex v : vertices) {
                if (v.x >= vcurr.x) {
                    dyt = v.y - vcurr.y;
                    dxt = v.x - vcurr.x;
                    if (compareSlope(dyt, dxt, dys, dxs) == -1) {
                        scmp = compareSlope(dyt, dxt, dyc, dxc);
                        lqt = dyt * dyt + dxt * dxt;
                        if (scmp >= 0) {
                            if (scmp > 0 || lqt > lqc) {
                                vnext = v;
                                dyc = dyt;
                                dxc = dxt;
                                lqc = lqt;
                            }
                        }
                    }
                }
            }
            if (vnext == null) {
                break;
            }
            dys = dyc;
            dxs = dxc;
            polygon.add(vnext);
            vertices.remove(vnext);
            vcurr = vnext;
            vnext = null;
        }
        dys = 1;
        dxs = 0;
        while (vcurr.x > sx) {
            dyc = -1;
            dxc = 0;
            lqc = 0;
            for (Vertex v : vertices) {
                if (v.x < vcurr.x) {
                    dyt = v.y - vcurr.y;
                    dxt = v.x - vcurr.x;
                    if (compareSlope(dyt, dxt, dys, dxs) == -1) {
                        scmp = compareSlope(dyt, dxt, dyc, dxc);
                        lqt = dyt * dyt + dxt * dxt;
                        if (scmp >= 0) {
                            if (scmp > 0 || lqt > lqc) {
                                vnext = v;
                                dyc = dyt;
                                dxc = dxt;
                                lqc = lqt;
                            }
                        }
                    }
                }
            }
            if (vnext == null) break;
            dys = dyc;
            dxs = dxc;
            polygon.add(vnext);
            vertices.remove(vnext);
            vcurr = vnext;
            vnext = null;
        }
        return polygon;
    }

    public int compareSlope(int dy2, int dx2, int dy1, int dx1) {
        if (dx2 != 0 && dx1 != 0) {
            double test = Double.valueOf(dy2 * dx1 - dy1 * dx2);
            return (int) Math.signum(test);
        } else {
            if (dx2 != 0 || dx1 != 0) {
                if (dx2 == 0) {
                    return dy2 >= 0 ? 1 : -1;
                } else {
                    return dy1 >= 0 ? -1 : 1;
                }
            } else {
                if (dy2 >= 0) {
                    return dy1 >= 0 ? 0 : 1;
                } else {
                    return dy1 >= 0 ? -1 : 0;
                }
            }
        }
    }
    public class Vertex {
        public int x;
        public int y;
        public Vertex(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public void PNGWrite(int[][] g, int pix, String output) {
        int[][] g1 = new int[g.length][g[0].length];
        int n = 0;
        for (int p = 0; p < g.length; p++) {
            for (int q = 0; q < g[0].length; q++) {
                if (g[p][q] == pix) {
                    g1[p][q] = g[p][q];
                    n += 2;
                } else {
                    g1[p][q] = 0;
                }
            }
        }
        int[] points = new int[n];
        int n1 = 0;
        //converxto vetx
        for (int p = 0; p < g1.length; p++) {
            for (int q = 0; q < g1[0].length; q++) {
                if (g1[p][q] != 0) {
                    points[n1++] = p;
                    points[n1++] = q;
                }
            }
        }
        List<Vertex> vertices = new Vector<Vertex>();
        for (int i1 = 0; i1 < points.length; i1 += 2) {
            Vertex v = new Vertex(points[i1], points[i1 + 1]);
            vertices.add(v);
        }
        //find
        long begin = System.currentTimeMillis();
        List<Vertex> polygon = convexHull(vertices);
        long elapsed = System.currentTimeMillis() - begin;
        seconds = elapsed / 1000.0;
        //converx to g[][]
        for (int p = 0; p < g1.length; p++) {
            for (int q = 0; q < g1[0].length; q++) {
                g1[p][q] = 0;
            }
        }
        for (int i1 = 0; i1 < polygon.size(); i1++) {
            g1[polygon.get(i1).x][polygon.get(i1).y] = 255;
        }
        new ReadWritePng().writePNG(output, g1);
    }
    public void CSVWrite(int[][] g, int pix, String outputcsv) {
        int[][] g1 = new int[g.length][g[0].length];
        int n = 0;
        for (int p = 0; p < g.length; p++) {
            for (int q = 0; q < g[0].length; q++) {
                if (g[p][q] == pix) {
                    g1[p][q] = g[p][q];
                    n += 2;
                } else {
                    g1[p][q] = 0;
                }
            }
        }
        int[] points = new int[n];
        int n1 = 0;
        //converxto vetx
        for (int p = 0; p < g1.length; p++) {
            for (int q = 0; q < g1[0].length; q++) {
                if (g1[p][q] != 0) {
                    points[n1++] = p;
                    points[n1++] = q;
                }
            }
        }
        List<Vertex> vertices = new Vector<Vertex>();
        for (int i1 = 0; i1 < points.length; i1 += 2) {
            Vertex v = new Vertex(points[i1], points[i1 + 1]);
            vertices.add(v);
        }
        //find
        long begin = System.currentTimeMillis();
        List<Vertex> polygon = convexHull(vertices);
        long elapsed = System.currentTimeMillis() - begin;
        seconds = elapsed / 1000.0;
        //converx to g[][]
        for (int p = 0; p < g1.length; p++) {
            for (int q = 0; q < g1[0].length; q++) {
                g1[p][q] = 0;
            }
        }
        for (int i1 = 0; i1 < polygon.size(); i1++) {
            g1[polygon.get(i1).x][polygon.get(i1).y] = 255;
        }
        try {
            File file = new File(outputcsv);
            FileOutputStream out = new FileOutputStream(file);
            OutputStreamWriter osw = new OutputStreamWriter(out, "GB2312");
            BufferedWriter bw = new BufferedWriter(osw);
            bw.write("cod_x" + ", " + "cod_y" + "\r\n");
            for (int i1 = 0; i1 < polygon.size(); i1++) {
                bw.write(polygon.get(i1).x + ", " + polygon.get(i1).y + "\r\n");
            }
            bw.close();
            osw.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
